; Write a function that returns union of two list and retains order. 
; new-union is that starting function.
(defun new-union (lst1 lst2)
  (cdr (reverse (union-order lst1 lst2 (list nil)))))

(defun union-order (lst1 lst2 result)
  (and (or lst1 lst2)
    (if (not (member (car lst1) result)) 
      (push (car lst1) result))
    (if (not (member (car lst2) result)) 
      (push (car lst2) result))
    (union-order (cdr lst1) (cdr lst2) result)))


;Write a function that return a list with number of times 
; an element is present in the list. The returned list should be 
; be sorted with number of times an element occurs. 
 
(defun occurrences (lst)
  (sort-output (run-thru-list lst (list))))

(defun run-thru-list (lst output)
  (if (consp lst)
    (let ((pair (assoc (car lst) output)))
      (if (null pair)
        (run-thru-list (cdr lst) (add-pair (car lst) output))
        (run-thru-list (cdr lst) (increment-pair pair output))))
    output))
      
       

(defun add-pair (item output)
  (cons (cons item 1) 
    output))   

(defun increment-pair (pair output)
  (cons 
    (cons (car pair) 
      (+ (cdr pair) 1)) 
    (remove pair output))) 

(defun sort-output (output)
  (sort output 
    #'(lambda (pair1 pair2)
      (> (cdr pair1) (cdr pair2)))))
